Cable networks were originally developed to facilitate the distribution of television broadcasts. Cable networks generally use coaxial cables as transmission lines for the dissemination of television broadcasts to various homes, businesses or other destinations. Cable networks were designed to support one-way communication of broadcast signals from a broadcast center to a number of television nodes connected to the cable network.
The “Internet” is a well-known term that refers to a collection of data networks that utilize layered protocols to route data packets to various locations around the world. The Internet carries and processes data traffic in Internet Protocol (IP) packets, each of which contains source and destination IP addresses, and other control information, along with a segment of user data (sometimes referred to as the payload). As such, computers use the Internet to communicate data in IP packets, and process IP packets in accordance with certain protocol.
The emergence of the Internet has prompted the desire to allow cable networks to support two-way packet-based data communication. This desire has resulted in standards and protocols that enable network infrastructure conventionally used for the distribution of cable television broadcasts to deliver Internet service to homes, businesses and other destinations. By adding the two-way packet based communication capability, cable networks can now support both one-way communication of cable television broadcasts and two-way packet based data communication.
In order to allow a cable network to offer Internet access to cable subscribers in a bandwidth-efficient manner, the Cable Television Laboratories (CableLab) has developed a series of Data Over Cable System Interface Specification (DOCSIS) standards that govern the design of cable modems (CMs) residing in subscribers' premises and of cable modem termination systems (CMTSs) deployed and managed by the cable operator. The network that interconnects the CMs to a CMTS is called the cable access network or DOCSIS network, which may physically consist of coaxial cables and optical fibers, and other transmission equipment, such as lasers and amplifiers, in the cable plant, which is commonly referred to as Hybrid Fiber-Coax (HFC) network.
For a cable subscriber to communicate over the Internet, it uses a DOCSIS-compliant CM to interface with the DOCSIS network. As the gateway to the Internet, the CMTS controls the access of the CM to the bandwidth resources of the DOCSIS network. Although a coaxial cable has a usable RF spectrum in excess of 500 MHz, most of this spectrum is used for broadcasting TV programs. Accordingly, only a small portion is typically allocated to transport data via the DOCSIS network. Current versions of DOCSIS include DOCSIS 1.0, DOCSIS 1.1 and DOCSIS 2.0. Future releases of DOCSIS may continue to evolve to improve the two-way packet-based communication and may entail more RF bandwidth for such services.
One challenge in DOCSIS and similar protocols, such as the wireless counterpart to DOCSIS that enables two-way packet based communication over a shared RF access medium, is the control and management of downstream communication. As referenced herein, “downstream communication” generally refers to communication from a CMTS to a CM. In contrast, “upstream communication” generally refers to communication from a CM to a CMTS. A DOCSIS network may have several upstream channels and several downstream channels, each using a unique RF spectrum that does not conflict with other channels. The CMTS implements a scheduler to control each respective channel. In particular, the CMTS may implement an upstream scheduler to control each upstream channel and a downstream scheduler to control each downstream channel.
In scheduling downstream communication, a downstream scheduler generally receives and schedules large bursts of downstream network traffic. To effectively forward the large burst of downstream network traffic, a downstream scheduler may implement complicated queuing algorithms to ensure adequate delivery rates to the CMs during periods of network congestion. In contrast, in the case of upstream communications packets generated by subscribers' computers are queued at their respective CMs while waiting to be transmitted over the DOCSIS upstream channel. As such, unlike the downstream scheduler, an upstream scheduler leverages on the DOCSIS Medium Access Control (MAC) protocol to control the traffic flow from CMs to the CMTS. As a CM can make only one bandwidth request for a packet at a time, the upstream scheduler does not experience the same packet queuing problem of the downstream scheduler. Downstream packet scheduling is further complicated by the dominant transport layer protocol, i.e., TCP, used for end-to-end data transport between subscribers' computers and content servers in the Internet. Upstream communications, however, are regulated by the DOCSIS MAC protocol and generally subscribers generate much less upstream traffic. Specifically, DOCSIS requires a CM to request time slots from a CMTS in order to perform upstream transmissions. The CMTS can reject these time slot requests in order to regulate upstream communications, thereby eliminating large upstream network traffic bursts.
Downstream bandwidth contention may arise due to the large bursts of downstream network traffic and result in occasional downstream traffic congestion at the CMTS. Short-term downstream traffic congestion leads to queuing delays while sustained congestion causes buffer overflows and packet losses. Queuing delays and packet losses are two main contributors to the degradation of the Quality of Service (QoS) of a downstream traffic flow. QoS is sometimes used to refer to a level of service that a CMTS agrees to deliver to a subscriber's CM. For example, DOCSIS defines QoS by a set of requirements that include a maximum downstream traffic rate and a minimum downstream traffic rate. Other DOCSIS QoS requirements include a maximum downstream packet latency. The downstream scheduler controls the QoS associated with each active downstream service flow, i.e., each flow of downstream traffic intended for a particular CM. For example, the downstream scheduler is responsible for determining which packets receive precedence over other packets during periods of congestion. DOCSIS compliant CMTSs include a downstream scheduler that adheres to DOCSIS specifications regarding QoS requirements.
Advanced downstream schedulers that attempt to achieve fair bandwidth allocation between subscribers typically implement one of two queuing algorithms. Both of these queuing algorithms implement approximate solutions of a known high-precision fair queuing algorithm, Weighted Fair Queuing (WFQ). WFQ idealistically seeks to ensure fair treatment of downstream traffic flows during periods of congestion, but implementations of WFQ result in fairness compromises due to the substantial computations needed to correctly implement WFQ. The two approximate solutions, Weighted Round-Robin (WRR) and Deficit Round-Robin (DRR), were designed to alleviate some of the complexity of WFQ, i.e., reduce the amount of needed computations.
In reducing the complexity of WFQ, both WRR and DRR may disregard one or more of the important QoS attributes including possibly some requirements put forth by DOCSIS. The downstream scheduler implementing WFQ, WRR, DRR, or some variation thereof, may, in certain heavily loaded situations, allocate bandwidth to large traffic flows, such as a long File Transfer Protocol (FTP) session, while disregarding queuing latency of smaller traffic flows, such as short HyperText Transfer Protocol (HTTP) download sessions, for which queuing latency is critical. These algorithms may also violate the DOCSIS minimum downstream traffic rate during periods of heavy loading. By not paying special attention to the smaller flows, the downstream scheduler may possibly cause these flows to retransmit due to excessive queuing latency.
Downstream schedulers implementing WFQ, WRR, DRR, or some other variation thereof, may also fail to incorporate other DOCSIS requirements or require separate algorithms to meet these DOCSIS requirements. These downstream schedulers may, for example, reduce complexity by not implementing adequate rate limiting mechanisms, i.e., mechanisms that enforce maximum rate limits, appropriately allocating bandwidth during periods of congestion, or any combination thereof. In other cases, these downstream schedulers may become very complex and computationally costly to implement if these downstream schedulers implement separate algorithms to meet the DOCSIS requirements. Moreover, these queuing algorithms fail to account for the expanding nature of TCP sessions, i.e., the nature of TCP to expand a session to exploit available bandwidth, which is not a DOCSIS requirement, yet poses a threat to ensuring the DOCSIS QoS requirements.
In addition to violating DOCSIS requirements, a downstream scheduler implementing WFQ, WRR, DRR, or some variation thereof, may experience, during periods of congestion, issues associated with managing complexity as the number of active downstream service flows increases. As the number of active downstream service flows increases, the typical downstream scheduler increases complexity by adding another queue for each active downstream service flow in accordance with the algorithms described above. An increase in complexity generally results in decreased performance of the downstream scheduler and possibly causes violation of DOCSIS requirements. For example, the downstream scheduler may increasingly violate minimum downstream traffic rates as the number of active downstream service flows increase. In this manner, a downstream scheduler implementing one of the queuing algorithms discussed above may not fairly assign downstream bandwidth, adequately manage TCP sessions, violate agreed upon downstream QoS requirements, and fail to adhere to other DOCSIS requirements.